package com.github.yangyishe.p100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 77. 组合
 * https://leetcode.cn/problems/combinations/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 *
 * 你可以按 任何顺序 返回答案。
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 4, k = 2
 * 输出：
 * [
 *   [2,4],
 *   [3,4],
 *   [2,3],
 *   [1,2],
 *   [1,3],
 *   [1,4],
 * ]
 * 示例 2：
 *
 * 输入：n = 1, k = 1
 * 输出：[[1]]
 *
 *
 * 提示：
 *
 * 1 <= n <= 20
 * 1 <= k <= n
 */
public class Problem77 {
    public static void main(String[] args) {
        int n=4,k=2;

        Problem77 problem77 = new Problem77();
        List<List<Integer>> combine = problem77.combine(n, k);
        System.out.println(combine);
    }

    /**
     * 思路:
     * 回溯.
     * 一个全局变量,一个结果集
     *
     * @param n
     * @param k
     * @return
     */
    public List<List<Integer>> combine(int n, int k) {
        tmp=new ArrayList<>();

        iterate(1,n,0,k);

        return resultList;
    }

    private void iterate(int startNum,int n,int tmpIndex,int k){
        if(tmpIndex==k){
            resultList.add(new ArrayList<>(tmp));
            return;
        }
        // 无论何时,i<=n
        // 此处边界理清略难, 需要考虑开闭区间; 也可以直接调试出来
        for(int i=startNum;i<=n-(k-tmpIndex)+1;i++){
            if(tmp.size()==tmpIndex){
                tmp.add(i);
            }else{
                tmp.set(tmpIndex,i);
            }
            iterate(i+1,n,tmpIndex+1,k);
        }
    }

    private List<Integer> tmp;

    private List<List<Integer>> resultList=new LinkedList<>();
}
